#include "vm/frame.h"
#include <debug.h>
#include <inttypes.h>
#include <round.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <hash.h>
#include <random.h>
#include "threads/pte.h"
#include "threads/init.h"
#include "threads/loader.h"
#include "threads/palloc.h"
#include "threads/malloc.h"
#include "threads/thread.h"
#include "threads/vaddr.h"
#include "filesys/filesys.h"
#include "userprog/pagedir.h"
#include "devices/timer.h"
#include "vm/page.h"
#include "vm/swap.h"

#define KERNEL_FRAME_PAGES 384
#define USER_FRAME_PAGES 384
#define KERNEL_FRAME_VADDR_BASE (LOADER_PHYS_BASE + 1024 * 1024)
#define USER_FRAME_VADDR_BASE (LOADER_PHYS_BASE + 1024 * 1024 + KERNEL_FRAME_PAGES * PGSIZE)

struct frame frame_table[USER_FRAME_PAGES];

static bool install_page(void *upage, void *kpage, bool writable);

struct lock frame_evict_lock;

// 初始化页框表中的所有页框
void init_frame(void)
{
  int i;
  lock_init(&frame_evict_lock);
  for (i = 0; i < USER_FRAME_PAGES; i++)
  {
    frame_table[i].frame_entry = NULL;
    frame_table[i].page = NULL;
    frame_table[i].type = -1;
    frame_table[i].u = false;
    frame_table[i].pin = false;
    lock_init(&frame_table[i].frame_lock);
  }
  return;
}

/* 选取table中的一个frame使其退出，返回其下标
选取算法为寻找type!=0且pin为false且u为false的frame，如果无符合要求随机返回 */
static int
frame_get_evict_no(void)
{
  int i, start = 2;
  // for (i = start; i < USER_FRAME_PAGES; i++)
  // {
  //   lock_acquire(&frame_table[i].frame_lock);
  //   if (frame_table[i].type == 0 || frame_table[i].pin)
  //   {
  //     lock_release(&frame_table[i].frame_lock);
  //     continue;
  //   }
  //   if (!frame_table[i].u)
  //   {
  //     frame_table[i].pin = true;
  //     lock_release(&frame_table[i].frame_lock);
  //     return i;
  //   }
  //   frame_table[i].u = false;
  //   lock_release(&frame_table[i].frame_lock);
  // }
  // for (i = start; i < USER_FRAME_PAGES; i++)
  // {
  //   lock_acquire(&frame_table[i].frame_lock);
  //   if (frame_table[i].type == 0 || frame_table[i].pin)
  //   {
  //     lock_release(&frame_table[i].frame_lock);
  //     continue;
  //   }
  //   if (!frame_table[i].u)
  //   {
  //     frame_table[i].pin = true;
  //     lock_release(&frame_table[i].frame_lock);
  //     return i;
  //   }
  //   lock_release(&frame_table[i].frame_lock);
  // }
  return 1 + random_ulong() % 383;
}

// 计算该物理地址frame_vaddr在frame_table中的index
int frame_get_no(uint32_t frame_vaddr)
{
  ASSERT(frame_vaddr != NULL);
  ASSERT(frame_vaddr >= USER_FRAME_VADDR_BASE);
  int no = (frame_vaddr - USER_FRAME_VADDR_BASE) / PGSIZE;
  return no;
}

// 页帧分配器：为虚拟地址page分配物理地址
void *
frame_allocator(uint8_t *page, bool writable)
{
  void *new_frame;

  // 用palloc_get_page获取内存中的物理地址，如果内存满了，用退出算法寻找一个页框退出，直到获取到new_frame
  while ((new_frame = palloc_get_page(PAL_USER)) == NULL)
  {
    // 用frame_get_evict_no退出算法寻找一个页框，用frame_evict_page使其退出
    lock_acquire(&frame_evict_lock);

    // 获取一个暂时不用的page在frame table的下标
    int no = frame_get_evict_no();

    // 把该page及相关东西swap out
    frame_evict_page(frame_table[no].page, true);
    lock_release(&frame_evict_lock);
  }
  ASSERT(new_frame != NULL);

  // 根据物理地址找到frame table的下标
  int fn = frame_get_no(new_frame);
  lock_acquire(&frame_table[fn].frame_lock);

  // 设置该frame
  frame_table[fn].frame_entry = new_frame;
  frame_table[fn].page = page;
  // struct page *p = page_lookup (&thread_current ()->page_table, pg_round_down (page));
  frame_table[fn].type = 0;
  frame_table[fn].u = true;

  // 把user virtual addr和kernel virtual addr联系起来，存在pintos自带的page table里
  if (!install_page(page, new_frame, writable))
    return NULL;

  frame_table[fn].pin = false;

  // 为物理地址fr分配内存空间
  memset(new_frame, 0, PGSIZE);
  lock_release(&frame_table[fn].frame_lock);
  return new_frame;
}

// 给虚拟地址addr分配对应的page和物理地址，page fault调用
bool frame_user_stack_grow(void *addr)
{
  // 找到虚拟地址addr对应块的起始地址
  void *sp_addr = pg_round_down(addr);

  // 给虚拟地址块sp_addr分配一个frame
  void *fr = frame_allocator(sp_addr, true);
  if (fr == NULL)
    return false;

  // 创建一个stack类型的page
  page_new_stack(&thread_current()->page_table, thread_current(), (uint8_t *)sp_addr); //把page放到线程的page_table中

  // 该page未被写过，dirty为false
  pagedir_set_dirty(thread_current()->pagedir, fr, false);

  return true;
}

// 在load时候调用，给page分配物理地址（page已经存在于该线程的page_table中）
bool frame_reload_page(uint8_t *page)
{
  // 根据虚拟地址找page结构体
  struct page *p = page_lookup(&thread_current()->page_table, pg_round_down(page));
  if (p == NULL)
    return false;

  // 检查page有没有物理地址
  void *frame_addr = pagedir_get_page(thread_current()->pagedir, page);
  if (frame_addr != NULL)
    return false;

  // 给page分配物理地址和frame，*fr为物理地址首地址
  void *fr = frame_allocator(pg_round_down(page), p->wirtable);

  // page在内存中
  if (p->sector == (block_sector_t)-1)
  {

    struct file *f = p->file;    // page的file
    unsigned offset = p->offset; // file的偏移量
    unsigned length = p->length; // 要从file读的长度

    // f != NULL说明page是file类型，找到该file并读入
    if (f != NULL)
    {
      file_seek(f, offset);
      file_read(f, fr, length);
    }

    // 用memset给fr+length开始分配内存
    memset(fr + length, 0, PGSIZE - length);
  }
  else
  {
    // 如果页p不在内存中，用swap_in交换到内存中
    swap_in(p, fr);
  }

  // 该page未被写过，dirty为false
  pagedir_set_dirty(thread_current()->pagedir, fr, false);

  return true;
}

// 把frame清空
void clear_frame(void *frame)
{
  int fn = frame_get_no(frame);
  lock_acquire(&frame_table[fn].frame_lock);
  frame_table[fn].frame_entry = NULL;
  frame_table[fn].page = NULL;
  frame_table[fn].type = -1;
  frame_table[fn].u = false;
  frame_table[fn].pin = false;
  lock_release(&frame_table[fn].frame_lock);
}

// 让page退出内存，frame_allocator内存满的时候和进程退出时和page_free调用
void frame_evict_page(uint8_t *page, bool swap)
{
  struct thread *t = thread_current();
  uint32_t *pd = t->pagedir;

  struct page *p = page_lookup(&t->page_table, page);

  // 检查page有没有物理地址，没有物理地址就返回
  void *frame_addr = pagedir_get_page(pd, page);
  if (frame_addr == NULL)
    return;

  // 把page的状态改成not present，再访问该page包含的地址时会产生page fault
  pagedir_clear_page(pd, page);

  int bytes;
  switch (p->data_type)
  {
  // mmap
  case 2:
    // 如果文件在内存里被修改过
    if (pagedir_is_dirty(pd, page))
    {
      // 把该修改写回原文件
      bytes = file_write_at(p->file, frame_addr, p->length, p->offset);
      break;
    }
  // file
  case 0:
    if (p->length != 0 && !pagedir_is_dirty(pd, page))
      break;
  // stack
  case 1:
    if (swap)
      // 如果内存满了，把传入的page移除内存
      swap_out(p, frame_addr);
  default:
    break;
  }

  clear_frame(frame_addr);
  palloc_free_page(frame_addr);

  return;
}

/* Adds a mapping from user virtual address UPAGE to kernel
   virtual address KPAGE to the page table.
   If WRITABLE is true, the user process may modify the page;
   otherwise, it is read-only.
   UPAGE must not already be mapped.
   KPAGE should probably be a page obtained from the user pool
   with palloc_get_page().
   Returns true on success, false if UPAGE is already mapped or
   if memory allocation fails. */
static bool
install_page(void *upage, void *kpage, bool writable)
{
  struct thread *t = thread_current();
  return (pagedir_get_page(t->pagedir, upage) == NULL && pagedir_set_page(t->pagedir, upage, kpage, writable));
}